1. Field if the Invention
The present invention relates to a transport management control apparatus and method for the same which in a unmanned carrier system such as that found in factories and the like, maintains the transport of unmanned carrier vehicles, and also determines the carrier route.
2. Background Art
FIG. 1 shows a constructional outline of an automated carrier system possessing a plurality of unmanned vehicles. In this figure, a transport management control apparatus 100 for conducting management of an unmanned carrier system, a passage type travel grid 101, and unmanned vehicles #1 to #5 are provided. In addition, on travel grid 101, a plurality of nodes 1, 2 . . . 28 exist, at which unmanned vehicles #1 to #5 stop, change directions, and unload their contents. In addition, each of unmanned vehicles #1 to #5 possesses a function for determining its travel route up until its individual target point (hereafter referred to as "target node"); these unmanned vehicles move over their individually-determined routes to their target nodes which are determined by means of transport management control apparatus 100. The detail description with respect to a technique for determining optimal route will be given later.
In the following, an example of this unmanned carrier system will be explained.
Initially, move designations are sent from transport management control apparatus 100 to unmanned vehicles #1 to #5 as shown in FIG. 1. These unmanned vehicles #1 to #5 then follow the optimal travel routes to respective target destinations. In this determination of the optimal route, the costs of each of the travel intervals (arcs) linking neighboring nodes are used, and the route which provides the minimum total cost value is selected. In the formation of this travel route, the travel routes of other unmanned vehicles are not taken into consideration; in other words, the optimal travel route of one unmanned vehicle is determined without considering the existence of other unmanned vehicles. In addition, the aforementioned costs represent characteristics such as the time required for transit of each arc, and the like. FIG. 2 shows the cost involved in travel grid 101; in this figure, the cost for each arc is shown in ().
FIGS. 3 and 4 show the travel route of each unmanned vehicle #1 to #5 formed at this time; FIG. 3 is a transport diagram showing the travel routes of each of unmanned vehicles #1 to #5 using a solid line, dotted line, short-dashed line, single-dotted chain line, and double-dotted chain line, respectively; FIG. 4 shows the aforementioned routes in node series.
Subsequently, unmanned vehicles #1 to #5 each independently send to transport management control apparatus 100 the node numbers on their respective traveling routes, in movement order, and the reservation of the nodes is then carried out. Transport management control apparatus 100 then examines in order the node series requested in the aforementioned (FIG. 4), and allows reservations from other unmanned vehicles in the case when nodes are not previously reserved. Unmanned vehicles #1 to #5 then move up to the allowable nodes. By means of this aforementioned control, collisions between the unmanned vehicles are avoided.
Given the scenario in which unmanned vehicles #1 to #5 have progressed to nodes 4, 6, 20, 22, and 3, respectively, FIG. 5 is a transport diagram showing the present positions and subsequent travel routes of each unmanned vehicle #1 to #5 at this time. However, at the time of the subsequent movement over the travel grid in the above-mentioned state, a competition for travel routes is generated in which unmanned vehicles #1 and #2 move in opposite directions on the same travel route. In this case, unless one of these unmanned vehicles changes routes, neither will be able to reach the desired target. In addition, at this time, neither of unmanned vehicles #1 and #2 will be allowed to reserve the node of their subsequent destination.
At this point, unmanned vehicle #1 finds a detour route (node 4.gtoreq.18.gtoreq.19.gtoreq.20.gtoreq.12.gtoreq.. . . ) and reserves node 18 and then moves to the reserved node. In this manner, it is then possible for unmanned vehicles #2 to move along its original route; however, another competition for travel routes is then generated between unmanned vehicles #1 and #3. FIG. 6 is a transport diagram showing the routes of unmanned vehicles #1 to #5 at this time. Accordingly, unmanned vehicle #3 locates a detour route (node 20.gtoreq.6.gtoreq.5.gtoreq.4.gtoreq.3.gtoreq.16.gtoreq.15), and then reserves and moves to node 6.
In the aforementioned manner, this competition for travel routes as well as search for detour routes is repeated, and unmanned vehicles #1 to #5 are then respectively moved to their desired destinations.
However, due to the change in movement routes resulting from competition for travel routes, wasteful movements and waiting periods are generated such as repeated searches for detour routes and the like. In addition, a significant problem exists in that as the number of vehicles increases, the carrier efficiency is drastically reduced.
Next, the description will be given with respect to the technique for determining an optimal route connecting a departure point and a target point in an unmanned carrier system.
The applicant of the present invention has previously proposed the method employing the structure shown in FIG. 7 (Japanese Patent Application No. Hei 3-141373) as an optimal route determining apparatus, in which at least the data establishment is complete, in unmanned carrier systems.
FIG. 7 shows the composition of an unmanned carrier vehicle; reference 16 indicates a map data memory which stores map data of the travel grid, and data relating to the nodes on the travel grid at which the unmanned carrier vehicle can stop, the coordinates thereof, or connection relationships are stored therein. Furthermore, reference numeral 17 indicates an unmanned vehicle data memory which stores data relating to the speed and the like of the unmanned carrier vehicles.
Furthermore, reference numeral 18 indicates a graph generator, which creates the graph GO shown below. EQU GO=(N, A, CO) (1)
Here, N={n.sub.1, n.sub.2, . . . , n.sub.m } indicates a set of all numbered nodes based on the mapped data: m indicates the node number.
A={a.sub.1, a.sub.2, . . . , a.sub.n } indicates a set of all arcs a.sub.k ={n.sub.i, n.sub.j }, numbered in order, connecting 2 freely selected adjoining nodes n.sub.i and n.sub.j which are used as an initial point and a final point, and between which travel is possible; n represents the are number.
CO represents a set of costs calculated based on cost calculation characteristics, such as the distance between nodes and the like, with respect to each are a.sub.k ={n.sub.i, n.sub.j }.
Reference 19 indicates an optimal route generator; it determines the departure node and target node from the carrying directive supplied to the unmanned carrier vehicles from a control unit, which is not depicted in the Figure. Next, this generator generates an optimal route which minimizes estimated costs based on the graph GO determined in the graph generator 18 and on the unmanned carrier vehicle data and map data.
Here, the cost calculation characteristics with respect to each are a.sub.k ={n.sub.i, n.sub.j } can include consideration of: (a) the distance between nodes, (b) the movement time between nodes, and in addition, (c) the directionality of the route.
In the case of (a), the cost B.sub.ij of the arc from the node i to the node j is determined as shown in formula (2) below. EQU B.sub.ij =d.sub.ij ( 2)
d.sub.ij represents the straight line distance (mm) between the initial point node i and the final point node j, and is expressed by: EQU d.sub.ij =((x.sub.j -x.sub.i).sup.2 +(y.sub.j -y.sub.i).sup.2).sup. 1/2( 3).
Here, x.sub.i and y.sub.i indicate the x and y coordinates (mm) of node 1, while x.sub.j and y.sub.j indicate the x and y coordinates (mm) of node j.
In the case of (b), the cost B.sub.ij of the arc from node i to node j is determined by means of the formula (4) below. EQU B.sub.ij =d.sub.ij /v.sub.ij ( 4)
The distance d.sub.ij is determined as shown above, while v.sub.ij represents the movement speed (m/sec) from node i to node j, so that B.sub.ij has an amount in correspondence with the movement time between the nodes.
In the case of (c), the cost B.sub.ij of the are from node i to node j is determined in accordance with the formula (5) as shown below. EQU B.sub.ij =(d.sub.ij /v.sub.ij).times.(1-p.sub.ij) (5)
Distance d.sub.ij and velocity v.sub.ij are determined as shown above, while P.sub.ij is a penalty coefficient expressing the "desirability" in accordance with the directionality of the route. For example, if the direction from node i to node j is an "undesirable" direction (opposite direction), then P.sub.ij is a negative number and the costs are raised, while when this direction is a "desirable" direction (normal direction) then P.sub.ij has a positive value, and it is possible to reduce the costs. The absolute value of the coefficient P.sub.ij is set within a range of "0-1" in accordance with the degree of desirability.
If appropriate penalty coefficients are established for all arcs, then it becomes possible to determine a single route having the smallest estimated costs (hereinbelow referred to as the shortest route) in the case in which 2 freely selected points (the departure point and the target point) are connected.
However, in order to appropriately establish penalty coefficients for all arcs, it was necessary to seriously consider the effects exerted on the route search by the penalty coefficient, and it was thus extremely complicated to establish such coefficients. However, when costs were calculated by means of the formulas (2) or (4), in which penalty coefficients were not considered, the following problems occurred.
Normally, travel grids have considerable regularity, such as the ladder shape shown in FIG. 8, or the square lattice shown in FIG. 9.
The lattice shaped travel grid shown in FIG. 8 is constructed from the node labeled "28". FIG. 10 shows the (x,y) coordinate data for each node.
FIG. 11 represents a compilation of the node numbers of the initial point and the final point, the direction, and the velocity data with respect to all scenes which are capable of adjoining movement in this lattice shaped travel grid. Herein, the directionality of the route is not considered and all directional data have a value of "0".
In addition, the movement velocity differs in the horizontal direction and the vertical direction, so that costs are calculated by means of formula (4), which takes account of movement velocity.
FIG. 12 shows the results of the calculation at the side of each arc. Herein, the costs of arcs in which the initial point and the final point are opposite is equal, so that for example, the costs of the arcs leading to nodes 1 and 2 are calculated by means of the following formula: ##EQU1## and are thus calculated to be "3000". Here, the reason why the velocity was divided by "1000" was in order to bring it in line with the units of formula (4). An identical calculation is performed with respect to the other arcs.
In order to determine the shortest route from node 1 to node 28 based on this data, the costs should be estimated for each arc along which travel is conducted and the route having the smallest total cost should be selected. However, here, as shown in FIG. 13, there are 8 shortest routes having equal total costs.
Furthermore, the ladder shaped travel grid shown in FIG. 9 is constructed from the node numbered "100". FIG. 14 shows the (x, y) coordinate data for each node.
Here, the movement velocity between the nodes is set to (1000 mm/sec) in all cases, and the scene data are omitted. Furthermore, the distance between adjoining nodes is set to 1 meter in all cases, so that the costs for each arc as calculated by means of formulas (2) or (4) have an identical value of (1000) in all cases.
Commonly, in ladder shaped travel grids having a number of columns p and a number of rows q, the number of shortest routes from the node at the lower left to the node at the upper right is determined by the following formula: EQU N(p,q)=.sub.p+q-2 C.sub.p-1 ( 6)
When the shortest route from node 1 to node 100 in the travel grid shown in FIG. 9 is calculated by means of this formula, then a number of routes shown by the following formula, which have identical conditions, are selected: ##EQU2##
When a calculation method is employed which is based solely on the distance between the nodes comprising each arc, or on the movement time, in this manner, than routes including directions which are normally undesirable, routes requiring frequent changes in direction, or the like, are all selected as identical conditions. Accordingly, it is difficult to determine the route which is optimal in actuality.